package com.jake.data_structure_learning.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * copyright (C), 2021, 北京同创永益科技发展有限公司
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/4/10 10:15
 * @description <author>                <time>                  <version>
 * WangXiang               2021/4/10 10:15            1.0.0
 */
public class Solution {


    /**
     * 二叉树的层序遍历
     * 示例：
     * 二叉树：[3,9,20,null,null,15,7],
     * <p>
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 返回其层序遍历结果：
     * <p>
     * [
     * [3],
     * [9,20],
     * [15,7]
     * ]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList();
        }
        Queue<List<TreeNode>> queue = new LinkedBlockingQueue<>();

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> rootList = new ArrayList<>();
        rootList.add(root.val);
        result.add(rootList);

        List<TreeNode> rootNodes = new ArrayList<>();
        rootNodes.add(root);
        queue.add(rootNodes);

        while (queue.peek() != null) {
            List<TreeNode> nodes = queue.poll();
            List<TreeNode> treeNodes = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            for (TreeNode node : nodes) {
                if (node.left != null) {
                    treeNodes.add(node.left);
                    list.add(node.left.val);
                }

                if (node.right != null) {
                    treeNodes.add(node.right);
                    list.add(node.right.val);
                }
            }
            if (!treeNodes.isEmpty()) {
                queue.add(treeNodes);
                result.add(list);
            }
        }
        return result;
    }


    public List<Integer> bfs(TreeNode root) {

        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedBlockingQueue<>();

        queue.add(root);

        while (queue.peek() != null) {
            TreeNode node = queue.poll();
            result.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }

//            System.out.println(node.val);


            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return result;
    }


    public List<List<Integer>> levelOrder2(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        result.add(list);

        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);

        while (queue.peek() != null) {
            int size = queue.size();
            if (size <= 0) {
                continue;
            }

            List<Integer> subList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                    subList.add(node.left.val);
                }
                if (node.right != null) {
                    queue.add(node.right);
                    subList.add(node.right.val);
                }
            }
            result.add(subList);
        }
        return result;
    }

    public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        helper(root, result, 0);
        return result;
    }

    public void helper(TreeNode node, List<List<Integer>> result, int level) {
        if (node == null) {
            return;
        }

        if (level == result.size()) {
            result.add(level, new ArrayList<>());
        }

        result.get(level).add(node.val);

        helper(node.left, result, level + 1);
        helper(node.right, result, level + 1);
    }


    /**
     * 左  中 右
     * 二叉树的中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        this.inorderTraversal(root, result);
        return result;
    }

    public void inorderTraversal(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            this.inorderTraversal(node.left, result);
        }
        result.add(node.val);
        if (node.right != null) {
            this.inorderTraversal(node.right, result);
        }
    }


    /**
     * 前序遍历
     * 根 左  右
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        this.preorderTraversal(root, result);
        return result;
    }

    public void preorderTraversal(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }

        result.add(node.val);

        if (node.left != null) {
            this.preorderTraversal(node.left, result);
        }

        if (node.right != null) {
            this.preorderTraversal(node.right, result);
        }
    }

    /**
     * 树对象
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public boolean isUgly(int n) {
        //   2   3  5
        if (n < 2) {
            return false;
        }

        if (n % 2 == 0) {
            return isUgly(n / 2);
        }

        if (n % 3 == 0) {
            return isUgly(n / 3);
        }

        if (n % 5 == 0) {
            return isUgly(n / 5);
        }
        return false;
    }

    public boolean helper(int n) {
        if (n < 2) {
            return false;
        }

        if (n % 2 == 0) {
            return helper(n / 2);
        }

        if (n % 3 == 0) {
            return helper(n / 3);
        }

        if (n % 5 == 0) {
            return helper(n / 5);
        }
        return false;
    }


    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return false;
        }

        TreeNode tempP = p;
        TreeNode tempQ = q;
        while (tempP != null && tempQ != null) {
            if (tempP.val != tempQ.val) {
                return false;
            }

            if (tempP.left.val != tempQ.left.val) {
                return false;
            }

            if (tempP.right.val != tempQ.right.val) {
                return false;
            }

//            tempP=tempP.
        }
        return false;
    }


}
